#!/usr/bin/env python
# -*- coding: utf-8 -*-

def find_least_cost_node(costs, processed):
    least_cost = float("inf")
    least_cost_node = None
    for node in costs.keys():
        if least_cost > costs[node] and node not in processed:
            least_cost = costs[node]
            least_cost_node = node
    return least_cost_node

def dijkstra(grahp, costs, parents, processed):
    node = find_least_cost_node(costs, processed)
    while(node is not None):
        neighbors = grahp[node]
        for neighbor in neighbors.keys():
            cost = costs[node] + neighbors[neighbor]
            if(neighbor not in costs or costs[neighbor] > cost):
                costs[neighbor] = cost
                parents[neighbor] = node
        processed.append(node)
        node = find_least_cost_node(costs, processed)

graph = {}
graph["A"] = {}
graph["A"]["B"] = 5
graph["A"]["C"] = 2

graph["B"] = {}
graph["B"]["D"] = 4

graph["C"] = {}
graph["C"]["D"] = 6
graph["C"]["E"] = 3

graph["D"] = {}
graph["D"]["F"] = 1

graph["E"] = {}
graph["E"]["F"] = 4

graph["F"] = {}

costs = {}
costs["A"] = 0

parents = {}
processed = []

dijkstra(graph, costs, parents, processed)
print(costs)
print(parents)